home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / geom_lib / ln_sweep.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  11KB  |  252 lines
  1. /******************************************************************************
  2. * Line plane sweep algorithm implementation - actual code.              *
  3. *                                          *
  4. * Written by:  Gershon Elber                              Ver 1.0, June 1993  *
  5. ******************************************************************************/
  6.  
  7. #include <stdio.h>
  8. #include <math.h>
  9. #include "irit_sm.h"
  10. #include "imalloc.h"
  11. #include "ln_sweep.h"
  12.  
  13. #define LS_XBBOX_OVERLAP(L1, L2) (L1 -> _MaxVals[0] > L2 -> _MinVals[0] && \
  14.                   L2 -> _MaxVals[0] > L1 -> _MinVals[0])
  15.  
  16. #if defined(ultrix) && defined(mips)
  17. static int LsSortCompare(VoidPtr Ptr1, VoidPtr Ptr2);
  18. #else
  19. static int LsSortCompare(const VoidPtr Ptr1, const VoidPtr Ptr2);
  20. #endif /* ultrix && mips (no const support) */
  21.  
  22. static void LsInitialize(LsLineSegStruct **Lines);
  23. static void LsIntersect(LsLineSegStruct *Lines);
  24. static int LsIntersectOne(LsLineSegStruct *L1, LsLineSegStruct *L2,
  25.               RealType *t1, RealType *t2);
  26.  
  27. /*****************************************************************************
  28. * DESCRIPTION:                                                               M
  29. * Computes all intersections between all given lines, in the plane.          M
  30. *   The Lines segments are updated so the Inters slot holds the list of      M
  31. * intersections with the other segments, NULL if none.                 M
  32. *   Returned is a list with possibly  a different order than that is given.  M
  33. *                                                                            *
  34. * PARAMETERS:                                                                M
  35. *   Lines:    To compute all intersections against each other, in the plane. M
  36. *                                                                            *
  37. * RETURN VALUE:                                                              M
  38. *   void                                                                     M
  39. *                                                                            *
  40. * KEYWORDS:                                                                  M
  41. *   LineSweep, line sweep, line line intersections                           M
  42. *****************************************************************************/
  43. void LineSweep(LsLineSegStruct **Lines)
  44. {
  45.     if (Lines == NULL || *Lines == NULL)
  46.     return;
  47.  
  48.     LsInitialize(Lines);
  49.     LsIntersect(*Lines);
  50. }
  51.  
  52. /*****************************************************************************
  53. * DESCRIPTION:                                                               *
  54. * A comparison routine for sorting two LsLineSegStructs with according to    *
  55. * _MinVals[1].                                                                 *
  56. *                                                                            *
  57. * PARAMETERS:                                                                *
  58. *   Ptr1, Ptr2:  Two pointers to two  LsLineSegStruct structures to compare. *
  59. *                                                                            *
  60. * RETURN VALUE:                                                              *
  61. *   int:   >0, 0, <0 as a result of the relation between the two structures. *
  62. *****************************************************************************/
  63. #if defined(ultrix) && defined(mips)
  64. static int LsSortCompare(VoidPtr Ptr1, VoidPtr Ptr2)
  65. #else
  66. static int LsSortCompare(const VoidPtr Ptr1, const VoidPtr Ptr2)
  67. #endif /* ultrix && mips (no const support) */
  68. {
  69.     RealType
  70.     Diff = ((*(LsLineSegStruct **) Ptr1)) -> _MinVals[1] -
  71.            ((*(LsLineSegStruct **) Ptr2)) -> _MinVals[1];
  72.  
  73.     return SIGN(Diff);
  74. }
  75.  
  76. /*****************************************************************************
  77. * DESCRIPTION:                                                               *
  78. * Initialize the necessary data structures for the plane sweep algorithm.    *
  79. *                                                                            *
  80. * PARAMETERS:                                                                *
  81. *   Lines:    To intersect against each other. Do initialize Lines in place. *
  82. *                                                                            *
  83. * RETURN VALUE:                                                              *
  84. *   void                                                                     *
  85. *****************************************************************************/
  86. static void LsInitialize(LsLineSegStruct **Lines)
  87. {
  88.     int i;
  89.     LsLineSegStruct *Line, **LineArray, **l;
  90.  
  91.     for (i = 0, Line = *Lines; Line != NULL; Line = Line -> Pnext, i++) {
  92.     RealType Size;
  93.  
  94.     Line -> _MinVals[0] = MIN(Line -> Pts[0][0], Line -> Pts[1][0]);
  95.     Line -> _MinVals[1] = MIN(Line -> Pts[0][1], Line -> Pts[1][1]);
  96.     Line -> _MaxVals[0] = MAX(Line -> Pts[0][0], Line -> Pts[1][0]);
  97.     Line -> _MaxVals[1] = MAX(Line -> Pts[0][1], Line -> Pts[1][1]);
  98.  
  99.     /* Computes the vector from first point to second. */
  100.     Line -> _Vec[0] = Line -> Pts[1][0] - Line -> Pts[0][0];
  101.     Line -> _Vec[1] = Line -> Pts[1][1] - Line -> Pts[0][1];
  102.  
  103.     /* Computes the line equation for the segment as Ax + By + C = 0,    */
  104.     /* sqrt(A^2 + B^2) = 1.                             */
  105.     Line -> _ABC[0] = Line -> _Vec[1];
  106.     Line -> _ABC[1] = -Line -> _Vec[0];
  107.     Size = sqrt(SQR(Line -> _ABC[0]) + SQR(Line -> _ABC[1]));
  108.     if (Size > 0.0) {
  109.         Line -> _ABC[0] /= Size;
  110.         Line -> _ABC[1] /= Size;
  111.         Line -> _ABC[2] = -(Line -> _ABC[0] * Line -> Pts[0][0] +
  112.                 Line -> _ABC[1] * Line -> Pts[0][1]);
  113.     }
  114.     else {
  115.         /* Zero length segment. Sets the line equation to never yield an */
  116.         /* intersection.                             */
  117.         Line -> _ABC[0] = Line -> _ABC[1] = 0.0;
  118.         Line -> _ABC[2] = 1.0;
  119.     }
  120.  
  121.     Line -> Inters = NULL;
  122.     }
  123.  
  124.     LineArray = (LsLineSegStruct **) IritMalloc(sizeof(LsLineSegStruct *) * i);
  125.     for (Line = *Lines, l = LineArray; Line != NULL; Line = Line -> Pnext)
  126.     *l++ = Line;
  127.     qsort(LineArray, i, sizeof(LsLineSegStruct *), LsSortCompare);
  128.     *Lines = *LineArray;
  129.     for (l = LineArray; --i; l++)
  130.     l[0] -> Pnext = l[1];
  131.     l[0] -> Pnext = NULL;
  132.     IritFree((VoidPtr) LineArray);
  133. }
  134.  
  135. /*****************************************************************************
  136. * DESCRIPTION:                                                               *
  137. *   The actual intersections. Not a real plane sweep, but close...         *
  138. * Marches along the given list and intersect every line with all lines in    *
  139. * the domain that can affect it.                         *
  140. *                                                                            *
  141. * PARAMETERS:                                                                *
  142. *   Lines:    To compute all intersections against each other, in the plane. M
  143. *                                                                            *
  144. * RETURN VALUE:                                                              *
  145. *   void                                                                     *
  146. *****************************************************************************/
  147. static void LsIntersect(LsLineSegStruct *Lines)
  148. {
  149.     static int
  150.     IdNumber = 0;
  151.     LsLineSegStruct *Line, *Line2;
  152.  
  153.     for (Line = Lines; Line -> Pnext != NULL; Line = Line -> Pnext) {
  154.     RealType t, t2,
  155.         MaxY = Line -> _MaxVals[1];
  156.  
  157.     for (Line2 = Line -> Pnext; Line2 != NULL; Line2 = Line2 -> Pnext) {
  158.         if (Line2 -> _MinVals[1] > MaxY)
  159.         break; /* Cannot intersect any more */
  160.  
  161.         if (Line -> Id != Line2 -> Id &&
  162.         LS_XBBOX_OVERLAP(Line, Line2) &&
  163.         LsIntersectOne(Line, Line2, &t, &t2)) {
  164.         LsIntersectStruct
  165.             *Inter = (LsIntersectStruct *)
  166.             IritMalloc(sizeof(LsIntersectStruct)),
  167.             *Inter2 = (LsIntersectStruct *)
  168.             IritMalloc(sizeof(LsIntersectStruct));
  169.  
  170.         Inter -> t = t;
  171.         Inter -> OtherT = t2;
  172.         Inter -> OtherSeg = Line2;
  173.         Inter -> Id = IdNumber;
  174.         Inter -> Pnext = Line -> Inters;
  175.         Line -> Inters = Inter;
  176.  
  177.         Inter2 -> t = t2;
  178.         Inter2 -> OtherT = t;
  179.         Inter2 -> OtherSeg = Line;
  180.         Inter2 -> Id = IdNumber++;
  181.         Inter2 -> Pnext = Line2 -> Inters;
  182.         Line2 -> Inters = Inter2;
  183.         }
  184.     }
  185.     }
  186. }
  187.  
  188. /*****************************************************************************
  189. * DESCRIPTION:                                                               *
  190. *   Computes a single intersection between two line segments.             *
  191. *   Returns TRUE if found an intersection and sets t1/t2 to the parameter    *
  192. * values of the intersection (t == 0 for first point, t == 1 for second).    *
  193. *                                                                            *
  194. *                                                                            *
  195. *                                                                            *
  196. * PARAMETERS:                                                                *
  197. *   L1:       First line to compute intersection with L2.                    *
  198. *   L2:       Second line to compute intersection with L1.                   *
  199. *   t1:       Parameter value of intersection location along L1.         *
  200. *   t2:       Parameter value of intersection location along L2.         *
  201. *                                                                            *
  202. * RETURN VALUE:                                                              *
  203. *   int:      TRUE if L1 and L2 actualy intersect, FALSE otherwise.          *
  204. *****************************************************************************/
  205. static int LsIntersectOne(LsLineSegStruct *L1,
  206.               LsLineSegStruct *L2,
  207.               RealType *t1,
  208.               RealType *t2)
  209. {
  210.     RealType Dist11, Dist12, Dist21, Dist22, XDiff, YDiff, Det;
  211.  
  212.     Dist11 = L1 -> _ABC[0] * L2 -> Pts[0][0] +
  213.          L1 -> _ABC[1] * L2 -> Pts[0][1] +
  214.          L1 -> _ABC[2];
  215.     Dist12 = L1 -> _ABC[0] * L2 -> Pts[1][0] +
  216.          L1 -> _ABC[1] * L2 -> Pts[1][1] +
  217.          L1 -> _ABC[2];
  218.     if (Dist11 * Dist12 > 0.0) /* L2's two end points are on same size of L1. */
  219.     return FALSE;
  220.  
  221.     Dist21 = L2 -> _ABC[0] * L1 -> Pts[0][0] +
  222.          L2 -> _ABC[1] * L1 -> Pts[0][1] +
  223.          L2 -> _ABC[2];
  224.     Dist22 = L2 -> _ABC[0] * L1 -> Pts[1][0] +
  225.          L2 -> _ABC[1] * L1 -> Pts[1][1] +
  226.          L2 -> _ABC[2];
  227.     if (Dist21 * Dist22 > 0.0) /* L1's two end points are on same size of L2. */
  228.     return FALSE;
  229.  
  230.     /* Solve the following linear system for t1 and t2.              */
  231.     /*                                      */
  232.     /* L1X1 + t1 L1Vx = L2X1 + t2 L2Vx                      */
  233.     /* L1Y1 + t1 L1Vy = L2Y1 + t2 L2Vy                      */
  234.     /*                                      */
  235.     /* or,                                  */
  236.     /*                                      */
  237.     /* t1 L1Vx - t2 L2Vx = L2X1 - L1X1                      */
  238.     /* t1 L1Vy - t2 L2Vy = L2Y1 - L1Y1                      */
  239.     /*                                      */
  240.     Det = L1 -> _Vec[1] * L2 -> _Vec[0] - L1 -> _Vec[0] * L2 -> _Vec[1];
  241.     if (Det == 0.0)
  242.     return FALSE;
  243.  
  244.     XDiff = L2 -> Pts[0][0] - L1 -> Pts[0][0];
  245.     YDiff = L2 -> Pts[0][1] - L1 -> Pts[0][1];
  246.  
  247.     *t1 = (YDiff * L2 -> _Vec[0] - XDiff * L2 -> _Vec[1]) / Det;
  248.     *t2 = (L1 -> _Vec[0] * YDiff - L1 -> _Vec[1] * XDiff) / Det;
  249.  
  250.     return *t1 > 0.0 && *t1 <= 1.0 && *t2 > 0.0 && *t2 <= 1.0;
  251. }
  252.